package com.tgy.leetcode;

/**
 * @Author: tgy
 * @Date: 12/8/20 2:19 PM
 *
 * https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof/
 */
public class _剑指_Offer_47_礼物的最大价值 {

    public int maxValue(int[][] grid) {


        int[] vals = new int[grid[0].length + 1];


        for (int i = 1; i <= grid.length; i++) {

            for (int j = 1; j <= grid[i - 1].length ; j++) {

                /**
                 * vals[j]:上一次已经计算好的值
                 *
                 * vals[j-1]: 当前行已经计算好的值
                 */
                vals[j] = Math.max(vals[j],vals[j - 1]) + grid[i - 1][j - 1];

            }
        }

        return vals[grid[0].length];
    }

    public int maxValue01(int[][] grid) {


        int[] vals = new int[grid[0].length];

        vals[0] = grid[0][0];
        for (int i = 1; i < grid[0].length; i++) {

            vals[i] = vals[i - 1] + grid[0][i];
        }

        for (int i = 1; i < grid.length; i++) {

            vals[0] += grid[i][0];
            for (int j = 1; j < grid[i].length; j++) {

                vals[j] = grid[i][j] + Math.max(vals[j - 1], vals[j]);
            }
        }

        return vals[grid[0].length  - 1];
    }
}
